package arithmetic.tree;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Queue;

public class BinaryTree implements Tree{
    //表示根节点
    private Node root;

    public Node getRoot() {
        return this.root;
    }


    //插入节点
    public boolean insert(int value) {
        Node newNode = new Node(value);
        if(root == null){//当前树为空树，没有任何节点
            root = newNode;
            return true;
        }else{
            Node current = root;
            Node parentNode = null;
            while(current != null){
                parentNode = current;
                if(current.value > value){//当前值比插入值大，搜索左子节点
                    current = current.left;
                    if(current == null){//左子节点为空，直接将新值插入到该节点
                        parentNode.left = newNode;
                        return true;
                    }
                }else{
                    current = current.right;
                    if(current == null){//右子节点为空，直接将新值插入到该节点
                        parentNode.right = newNode;
                        return true;
                    }
                }
            }
        }
        return false;
    }

    //中序遍历
    public void infixOrder(Node current){
        if(current != null){
            infixOrder(current.left);
            System.out.print(current.value+" ");
            infixOrder(current.right);
        }
    }

    //前序遍历
    public void preOrder(Node current){
        if(current != null){
            System.out.print(current.value+" ");
            infixOrder(current.left);
            infixOrder(current.right);
        }
    }

    //后序遍历
    public void postOrder(Node current){
        if(current != null){
            infixOrder(current.left);
            infixOrder(current.right);
            System.out.print(current.value+" ");
        }
    }

    //层序遍历
    public void cengXuPrint(Node t) {
        Queue<Node> q1 = new ArrayDeque<Node>();
        if (t == null)
            return;
        if (t != null) {
            q1.add(t);
        }
        int currentLine=1;
        int nextLine=0;
        while (!q1.isEmpty()) {
            Node t1 = q1.poll();
            currentLine--;
            System.out.print( t1.value+" ");
            if (t1.left != null){
                q1.add(t1.left);
                nextLine++;
            }
            if (t1.right != null){
                q1.add(t1.right);
                nextLine++;
            }
            if (currentLine == 0) {
                System.out.println();
                currentLine=nextLine;
                nextLine=0;
            }
        }
    }

    //层序遍历
    public void cengXu(Node t) {
        Queue<Node> q1 = new ArrayDeque<Node>();
        q1.add(t);
        while (!q1.isEmpty()) {
            Node t1 = q1.poll();
            if (t1.left != null)
                q1.add(t1.left);
            if (t1.right != null)
                q1.add(t1.right);
            System.out.print(t1.value + " ");
        }
    }

    //找到最大值
    public Node findMax(){
        Node current = root;
        Node maxNode = current;
        while(current != null){
            maxNode = current;
            current = current.right;
        }
        return maxNode;
    }
    //找到最小值
    public Node findMin(){
        Node current = root;
        Node minNode = current;
        while(current != null){
            minNode = current;
            current = current.left;
        }
        return minNode;
    }

    //查找节点
    public Node find(int key) {
        Node current = root;
        while(current != null){
            if(current.value > key){//当前值比查找值大，搜索左子树
                current = current.left;
            }else if(current.value < key){//当前值比查找值小，搜索右子树
                current = current.right;
            }else{
                return current;
            }
        }
        return null;//遍历完整个树没找到，返回null
    }

    @Override
    public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        boolean isleft = false;
        //查找删除值，找不到直接返回false
        while(current.value != key){
            parent = current;
            if(current.value > key){
                isleft = true;
                current = current.left;
            }else{
                isleft = false;
                current = current.right;
            }
            if(current == null){
                return false;
            }
        }
        //如果当前节点没有子节点
        if(current.left == null && current.right == null){
            if(current == root){
                root = null;
            }else if(isleft){
                parent.left = null;
            }else{
                parent.right = null;
            }
            return true;

            //当前节点有一个子节点，右子节点
        }else if(current.left == null && current.right != null){
            if(current == root){
                root = current.right;
            }else if(isleft){
                parent.left = current.right;
            }else{
                parent.right = current.right;
            }
            return true;
            //当前节点有一个子节点，左子节点
        }else if(current.left != null && current.right == null){
            if(current == root){
                root = current.left;
            }else if(isleft){
                parent.left = current.left;
            }else{
                parent.right = current.left;
            }
            return true;
        }else{
            //当前节点存在两个子节点
            Node successor = getSuccessor(current);
            if(current == root){
                successor = root;
            }else if(isleft){
                parent.left = successor;
            }else{
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return false;

    }

    public Node getSuccessor(Node delNode){
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.right;
        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.left;
        }
        //后继节点不是删除节点的右子节点，将后继节点替换删除节点
        if(successor != delNode.right){
            successorParent.left = successor.right;
            successor.right = delNode.right;
        }

        return successor;
    }





}
